/*
直接插入排序是一边比较一边移动，折半插入是先折半查找合适的位置然后再一次性移动

平均时间复杂度：折半查找O(NlogN) + 移动O(N^2) ~ O(N^2)
空间复杂度：O(1)

稳定排序：是
原地排序：是
*/
#include "../../include/common.h"

void BinaryInsertSort(ElementType a[], int n){
    int i, j, low, high, mid;
    ElementType x;
    for (i=1; i<n; i++){
        if (a[i] < a[i-1]){
            x = a[i];   // 标记当前元素
            // 折半查找
            low = 0;
            high = i-1;
            while (low <= high){
                mid = (low + high) / 2;
                if (a[mid] > x)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            // 移动元素
            for (j = i-1; j>=high+1; j--){
                a[j+1] = a[j];
            }
            a[high+1] = x;
        }
    }
}